package a.codetop.DP;

import org.junit.Test;

public class 最长公共子串 {
    @Test
    public void test() {
        System.out.println(LCS("1AB2345CD", "12345EF"));
    }

    public String LCS (String s1, String s2) {
        //一定含i,j 的 0~i和0~j的最长公共子串长度
        int[][] dp = new int[s1.length()][s2.length()];

        //base:最多一个相同
        for (int i = 0; i < s1.length(); i++) {
            dp[i][0]= s1.charAt(i)==s2.charAt(0)?1:0;
        }
        for (int j = 0; j < s2.length(); j++) {
            dp[0][j]= s1.charAt(0)==s2.charAt(j)?1:0;
        }

        int maxLen = 0;
        String maxStr = s1.charAt(0)+""; //公共子串至少是一个字符

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if(s1.charAt(i)!=s2.charAt(j)) dp[i][j]=0;
                //虽然看着像子序列，但是这是子串。因为i-1!=j-1时上一个自动为0，当前ij=1正确
                else{
                    dp[i][j]=dp[i-1][j-1]+1;
                    if(dp[i][j]>maxLen) {
                        maxLen = dp[i][j];
                        maxStr = s1.substring(i+1-dp[i][j],i+1);
                    }
                }
            }
        }

        return maxStr;
    }

}
